Technical Field
The present invention relates generally to generating and processing a 3D graphics dataset, and more specifically to organizing and rendering 3D voxel models in a tree data structure.
Description of the Related Art
Three-dimensional (“3D”) digital data may be produced by a variety of devices that involve three-dimensional scanning, sampling and/or numerical modeling. For example, laser scanners generate 3D digital data. A long range laser scanner is fixed in one location and rotated to scan objects around it. Alternatively, a short range laser scanner is mounted on a device that moves around an object to be scanned. In either case, the location of each point scanned is represented as a polar coordinate since the angle between the scanner and the object and distance from the scanner to the object are known. Typically the polar coordinates are then converted to 3D Cartesian coordinates and stored along with a corresponding intensity or color value for the data point collected by the scanner.
As described above, a 3D scanning/sampling/modeling device may generate 3D digital data by collecting a complete set of (x, y, z) locations that represent the shape of an object. The term “point cloud” is used to describe such point sets including a large number of points. The data points in point cloud data are unorganized and spaced irregularly within the cloud. While in some applications point cloud data can directly be used to generate 3D images, in other applications point cloud data can be transformed to volume graphics or 3D voxel data, which can then be used to generate 3D images. Some exemplary systems and methods for transforming point cloud data to volume graphics data are disclosed in commonly owned U.S. Pat. Nos. 7,317,456 B1 and 7,420,555 B1 both entitled “METHOD AND APPARATUS FOR TRANSFORMING POINT CLOUD DATA TO VOLUMETRIC DATA,” which are incorporated herein by reference. In volume graphics, volume elements (i.e., “voxels”) are the base data used to represent 3D objects. Typically, voxels are simply pixels that have a third coordinate z in addition to x and y coordinates in a Cartesian coordinate system (though voxels may take various other forms, also). In other words, voxels are equally sized cubes that form a discretely defined 3D space.
Volume graphics represent a promising way to achieve the degree of realism required for high quality 3D simulations and visualization applications because volume models can contain all the surface and internal characteristics of a real object. This is in contrast to, for example, polygon-based graphics, in which a mesh of polygons is used to represent only the surfaces of a 3D object.
3D voxel data are rendered to produce a 2D image on a suitable output device, such as a display or a printer. As used herein, the term “render” means to produce a 2D graphics image on an output device (e.g., a display screen) from a 3D graphics data model, and typically involves creating an image using various “attributes” such as color, normal (which indicates a direction of illumination to define shine), intensity (brightness/darkness), texture, etc., to give the image a realistic look.
Software available from NGRAIN (Canada) Corp. of Vancouver B.C., Canada, is suited for generating voxel data which can be rapidly rendered and also readily manipulated in real time. Briefly, NGRAIN® technology permits 3D modeling of an object, wherein each of multiple parts or layers forming the object is represented as a voxel set each consisting of one or more voxels. According to NGRAIN® technology, it is possible to render a large number of voxel sets representing multiple parts or layers together, while allowing a user to manipulate each part or layer separately in 3D space. For example, the user may break up the parts or layers to display an exploded view of an object, or may peel off an outer layer of the object to reveal its inner layer. Various details of NGRAIN® technology are described in commonly owned Patent Cooperation Treaty Publication No. WO 02/07088 A2 entitled “LIGHTING ADJUSTMENT METHODS AND APPARATUS FOR VOXEL DATA,” commonly owned Patent Cooperation Treaty Publication No. WO 02/07089 A2 entitled “APPARATUS AND METHOD FOR ASSOCIATING VOXEL INFORMATION WITH DISPLAY POSITIONS,” commonly owned U.S. Pat. No. 6,867,774 B1 entitled “METHOD AND APPARATUS FOR TRANSFORMING POLYGON DATA TO VOXEL DATA FOR GENERAL PURPOSE APPLICATIONS,” commonly owned U.S. Pat. No. 7,050,054 B2 entitled “METHOD, APPARATUS, SIGNALS AND CODES FOR ESTABLISHING AND USING A DATA STRUCTURE FOR STORING VOXEL INFORMATION,” commonly owned U.S. Pat. No. 7,218,323 B1 entitled “METHOD AND SYSTEM FOR RENDERING VOXEL DATA WHILE ADDRESSING MULTIPLE VOXEL SET INTERPENETRATION,” commonly owned U.S. Pat. No. 7,965,290 B1 entitled “METHOD, SYSTEM, AND DATA STRUCTURE FOR PROGRESSIVE LOADING AND PROCESSING OF A 3D DATASET,” and commonly owned U.S. Pat. No. 8,217,939 B1 entitled “METHOD AND SYSTEM FOR CALCULATING VISUALLY IMPROVED EDGE VOXEL NORMALS WHEN CONVERTING POLYGON DATA TO VOXEL DATA,” which are all incorporated herein by reference. Additional details of NGRAIN® technology can also be found in an article entitled “Myths and Truths of Interactive Volume Graphics” published in I/ITSEC 2004 Conference, and in an article entitled “Applying Volume Graphics in a Maintenance Training Environment” published in I/ITSEC 2005 conference.